
public class BinarySearchTree {

    //节点
    static class TreeNode{
        int key;
        TreeNode left;
        TreeNode right;

        public TreeNode(int key){
            this.key = key;
        }
    }

    //根节点
    TreeNode root;

    //搜索节点
    public TreeNode search(int key){
        TreeNode cur = root;

        //根节点为空
        if(root == null){
            return root;
        }

        //根节点不为空
        TreeNode parent = null;
        while(cur != null){
            if(cur.key == key){
                return cur;
            }else if(cur.key > key){
                parent = cur;
                cur = cur.left;
            }else{
                parent = cur;
                cur = cur.right;
            }
        }
        //找不到
        return null;
    }

    //增加方法
    public boolean put(int key){
        TreeNode cur = root;

        //根节点为空
        if(root == null){
            root = new TreeNode(key);
            return true;
        }

        //根节点不为空
        TreeNode parent = null;
        while(cur != null){
            //不能添加
            if(cur.key == key){
                return false;
            }else if(cur.key > key){
                parent = cur;
                cur = cur.left;
            }else{
                parent = cur;
                cur = cur.right;
            }
        }

        //开始添加
      //添加在左边
        if(parent.key > key){
            parent.left = new TreeNode(key);
        } //添加在右边
        else {
            parent.right = new TreeNode(key);
        }
        return true;
    }

    //删除节点
    public boolean remove(int key) {
        //根节点为空
        if (root == null) {
            return false;
        }
        TreeNode cur = root;
        TreeNode parent = null;

        //找到key节点的位置
        while (cur != null) {
            if (cur.key == key) {
                break;
            } else if (cur.key > key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }

        if (cur == null) {
            return false;
        }

        //三种情况
        //1.节点有左边，没有右边
        if (cur.left != null && cur.right == null) {
            //节点等于根节点
            if (cur == root) {
                cur = root.left;
            }//节点在父节点的左边
            else if (cur == parent.left) {
                parent.left = cur.right;
            }//节点在父节点的右边
            else {
                parent.right = cur.right;
            }
        }//节点有右边,没有左边
        else if (cur.left == null && cur.right != null) {
            //节点等于根节点
            if (cur == root) {
                root = root.right;
            }//节点在父节点的左边
            else if (parent.left == cur) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        }//都存在
        //参考写的法二：
        else {
            //定义目标节点
            TreeNode target = cur.right;
            TreeNode targetNodeParent = cur;

            while (target.left != null) {
                targetNodeParent = target;
                target = target.left;
            }

            //找到了，替换
            cur.key = target.key;

            //改变节点
            if (cur.right == target) {
                cur.right = target.right;
            } else {
                targetNodeParent.left = target.right;
            }
        }
        return true;
    }
    public void display(){
        TreeNode cur = root;
        System.out.print("[ ");
        print1(root);
        System.out.println("]");
    }

    private void print1(TreeNode root){
        if(root == null) return;

        print1(root.left);
        System.out.print(root.key + " ");
        print1(root.right);
    }
    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.put(1);
        binarySearchTree.put(2);
        binarySearchTree.remove(1);
        System.out.println(binarySearchTree.search(1));
        binarySearchTree.display();

    }

        //自己写的法一：
       /* else{
            //找到节点中右子树的最小节点进行替换
            TreeNode replace = rightMinKey(cur.right);
            cur.key = replace.key;

            if(cur.right == replace){
                cur.right = replace.right;
            }

        }
       return true;
    }
    private TreeNode rightMinKey(TreeNode node){
        TreeNode parent = null;
        while(node.left != null){

            parent = node;
            node = node.left;

        }
        if(parent != null)
        parent.left = node.right;
        return node;
    }*/
}
